package basic.study.leetcode;

import java.util.*;

public class Hard224 {

    public static void main(String[] args) {
        //System.out.println(calculate("(1+(4+5+2)-3)+(6+8)"));
        System.out.println(fuck(" 2*3 + 4 "));
    }


    // 1. 中序表达式转换为后续表达式 -- 调度场算法
    // 2. 逆波兰求解 https://leetcode-cn.com/problems/basic-calculator/solution/zhong-xu-hou-xu-ni-bo-lan-java-by-voiddme/
    public static int calculate(String s) {
        Stack<String> stack = new Stack<>();
        Queue<String> queue = new LinkedList<>();

        // 中序表达式转化为后续表达式
        // 1. 符号优先级大于栈顶元素，则入栈，否则将栈顶优先级高或相等的元素全部出栈，然后入栈
        // 2. 左括号优先级最高，直接入栈
        // 3. 右括号优先级最低，需要将栈顶元素出栈，直到遇到左括号（左括号也需要出栈）
        for (int i = 0; i < s.length(); i++) {
            String c = String.valueOf(s.charAt(i));

            if (c.equals(" ")) continue ;
            if (c.equals("(")) stack.push("(");
            else if (c.equals(")")) {
                while (!stack.peek().equals("(")) queue.offer(stack.pop()); // 左括号前的所有元素出栈
                stack.pop(); // 右括号出栈
            } else if (c.equals("+") || c.equals("-")) {
                if (!stack.isEmpty() && !stack.peek().equals("(")) { // 优先级相等或较高，出栈
                    queue.offer(stack.pop());
                }
                stack.push(c);
            } else {
                int num = s.charAt(i) - '0';
                while (i+1 < s.length() && Character.isDigit(s.charAt(i+1))) {
                    num = (num*10 + s.charAt(i+1)-'0');
                    i++;
                }
                queue.offer(String.valueOf(num));
            }
        }
        while (!stack.isEmpty()) queue.offer(stack.pop());

        // 逆波兰求解
        Stack<Integer> stack2 = new Stack<>();
        while (!queue.isEmpty()) {
            String token  = queue.poll();
            if (token.equals("+")) {
                stack2.push(stack2.pop() + stack2.pop());
            } else if (token.equals("-")) {
                stack2.push(-stack2.pop() + stack2.pop());
            } else {
                stack2.push(Integer.valueOf(token));
            }
        }
        return stack2.pop();
    }


    public static int calculate1(String s) {
        Stack<Integer> stack = new Stack<>();
        Integer res=0,sign=1,cur;
        for(int i=0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(Character.isDigit(ch)) {
                cur = ch - '0';
                    while(i+1 < s.length() && Character.isDigit(s.charAt(i+1))) {
                        cur = cur *10 + s.charAt(++i) - '0';
                    }
                res += sign * cur;
            }
            else if(ch == '+') {
                sign = 1;
            }else if(ch == '-') {
                sign = -1;
            }else if(ch == '(') {
                stack.push(res);
                res = 0;
                stack.push(sign);
                sign = 1;
            }else if(ch == ')') {
                res = res * stack.pop() + stack.pop();
            }
        }
        return res;
    }
    //" 3+5 / 2 "
    public static int fuck(String s) {
        //方法1，逆序波兰（我懒不写了）
        //方法2，直接中序双栈法，等级制度,我试试
        Stack<String> stack = new Stack<>();
        Stack<Integer> data = new Stack<>();
        Integer i1,i2,cur;
        for(int i=0;i<s.length(); i++) {
            String ss = String.valueOf(s.charAt(i));
            if(Character.isDigit(s.charAt(i))) {
                //补,两位数
                cur = Integer.valueOf(ss);
                while(i+1<s.length() && Character.isDigit(s.charAt(i+1))) {
                    cur = cur * 10 + s.charAt(++i) - '0';
                }
                data.push(cur);
            }else if(ss.equals("*") || ss.equals("/")) {
                if(stack.empty()) {
                    stack.push(ss);
                }else {//查询是否有同级，有的话先执行
                    if (stack.peek().equals("*") || stack.peek().equals("/")) {
                        if (stack.peek().equals("/")) {
                            i1 = data.pop();
                            i2 = data.pop();
                            data.push(i2 / i1);
                            stack.pop();
                        } else {
                            i1 = data.pop();
                            i2 = data.pop();
                            data.push(i2 * i1);
                            stack.pop();
                        }
                    }
                    stack.push(ss);
                }
            }else if(ss.equals("+") || ss.equals("-")) {
                if(stack.empty()) {

                }//若有高级的，先执行高级的
                else if(stack.peek().equals("*") || stack.peek().equals("/")) {
                    if(stack.peek().equals("/")){
                        i1 = data.pop();
                        i2 = data.pop();
                        data.push(i2 / i1);
                        stack.pop();
                    }else {
                        i1 = data.pop();
                        i2 = data.pop();
                        data.push(i2 * i1);
                        stack.pop();
                    }
                }
                //若有同级的，先执行，然后再push
                while(!stack.empty() && (stack.peek().equals("+")|| stack.peek().equals("-") )){
                    if(stack.peek().equals("+")){
                        data.push(data.pop() + data.pop());
                        stack.pop();
                    }
                    else if(stack.peek().equals("-")){
                        data.push(-data.pop() + data.pop());
                        stack.pop();
                    }
                }
                stack.push(ss);

            }else {
                continue;
            }
        }
        //最后
        if(!stack.empty()){
            if(stack.peek().equals("/")){
                i1 = data.pop();
                i2 = data.pop();
                data.push(i2 / i1);
                stack.pop();
            }else if(stack.peek().equals("*")){
                i1 = data.pop();
                i2 = data.pop();
                data.push(i2 * i1);
                stack.pop();
            }
        }
        if(!stack.empty()) {
            if(stack.peek().equals("+")){
                data.push(data.pop() + data.pop());stack.pop();
            }
            else if(stack.peek().equals("-")){
                data.push(-data.pop() + data.pop());stack.pop();
            }
        }
        return data.pop();
    }
}